package com.leetcode.algorithm.二叉树;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class lc94二叉树的中序遍历 {

    public static String line;
    public static String[] parts;
    public static int n;


    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while((line=in.readLine())!=null){
            parts=line.split(" ");
            n= parts.length;
            String[] levelOrder =new String[n];
            for (int i = 0; i <n; i++) {
                levelOrder[i]= parts[i];
            }
            TreeNode root = createTree(levelOrder);
            out.println(inorderTraversal(root));
            out.flush();
        }
        out.close();
    }

    private static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res =new ArrayList<>();
        dfs(root,res);
        return res;
    }

    private static void dfs(TreeNode root, List<Integer> res) {
        if(root==null) return;
        dfs(root.left,res);
        res.add(root.val);
        dfs(root.right,res);
    }

    private static TreeNode createTree(String[] levelOrder) {
        if (levelOrder.length == 0 || levelOrder[0].equals("null")) {
            return null;
        }
        TreeNode[] nodes = new TreeNode[n];
        for (int i = 0; i < n; i++) {
            if (!levelOrder[i].equals("null")) {
                nodes[i] = new TreeNode(Integer.parseInt(levelOrder[i]));
            }else{
                nodes[i]=null;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nodes[i] != null) {
                int leftIndex = 2 * i + 1;
                int rightIndex = 2 * i + 2;
                if (leftIndex < n) nodes[i].left = nodes[leftIndex];
                if (rightIndex < n) nodes[i].right = nodes[rightIndex];
            }
        }
        return nodes[0];
    }
}
